package com.bascker.algorithm.practice.arr.easy.third_max;

import java.util.Arrays;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;

// 线性扫描: 类似 maximum_product#Solution 的解法
// 时间复杂度	O(n)，空间复杂度	O(1)
// 缺点：对于边界场景不容易考虑到，一旦考虑缺失，就没法 AC
public class Solution1 {

    public int thirdMax(int[] nums) {
        if (Objects.isNull(nums)) {
            return 0;
        }

        // 去重：去除重复元素的影响
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());

        /// 线性扫描：直接找到最大的 3 个数
        int max1 = Integer.MIN_VALUE;

        // 边界值场景1：处理元素中存在 Integer.MIN_VALUE 值的情况
        long max2 = Long.MIN_VALUE, max3 = Long.MIN_VALUE;
        for (int x : set) {
            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
        }

        // 边界值场景2：处理无第三大元素的情况
        if (set.size() < 3) {
            return max1;
        }

        return max3 == Long.MIN_VALUE ? max1 : (int) max3;
    }

}
